package leetcode.lcp0034;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {
	int max;

	public int maxValue(TreeNode root, int k) {
		this.max = k;
		Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
		return this.max(root, k, dp);
	}

	private int max(TreeNode root, int k, Map<Integer, Map<Integer, Integer>> dp) {
		if (root == null) {
			return 0;
		}
		int hash = root.hashCode();
		if (dp.containsKey(hash) && dp.get(hash).containsKey(k)) {
			return dp.get(hash).get(k);
		}
		int ans = 0;
		for (int i = 0; i <= k - 1; i++) {
			ans = Math.max(ans, root.val + this.max(root.left, i, dp) + this.max(root.right, k - i - 1, dp));
		}
		int ans1 = 0;
		for (int i = 0; i <= max; i++) {
			ans1 = Math.max(ans1, this.max(root.left, i, dp));
		}
		int ans2 = 0;
		for (int i = 0; i <= max; i++) {
			ans2 = Math.max(ans2, this.max(root.right, i, dp));
		}
		ans = Math.max(ans, ans1 + ans2);
		Map<Integer, Integer> val = dp.getOrDefault(hash, new HashMap<>());
		val.put(k, ans);
		dp.put(hash, val);
		return ans;
	}

	@Override
	public void debug4() {
		TreeNode root = new TreeNode();
		H.compare(11, this.maxValue(TreeArray.array2tree(H.str2array4("[5,2,2,4]")), 2));
		H.compare(12, this.maxValue(TreeArray.array2tree(H.str2array4("[5,2,3,4]")), 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
